The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A (k, g)‐cage is a k‐regular graph with girth g that has the fewest number of vertices. It has been conjectured (Fu et al., J Graph Theory 24 (1997), 187–191) that all (k, g)‐cages are k‐connected for k ≥ 3. A connected graph G is said to be superconnected if every minimum cut‐set S is the neighborhood of a vertex of minimum degree. Moreover, if G‐S has precisely two components, then G is called tightly...
We provide first‐time fixed‐parameter tractability results for the NP‐hard problems MAXIMUM FULL‐DEGREE SPANNING TREE (FDST) and MINIMUM‐VERTEX FEEDBACK EDGE SET. These problems are dual to each other. In MAXIMUM FDST, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For MINIMUM‐VERTEX FEEDBACK EDGE SET, the task is to minimize...
A transposition graph is a Cayley graph in which each vertex corresponds to a permutation and an edge is placed between permutations iff they differ by exactly one transposition. In this article, we propose an efficient algorithm to find a collection of vertex‐disjoint paths connecting a given source vertex s and a given set of destination vertices D. The running time of the algorithm is polynomial...
Connectivity augmentation problems ask for adding a set of at most k edges (called links) whose insertion makes a given graph satisfy a specified connectivity property, such as bridge‐connectivity or biconnectivity. A bridge‐connected (biconnected) graph is a connected graph that does not possess an edge (a vertex) whose removal results in a disconnected graph. We show that, for bridge‐connectivity...
We study the connectivity and diameter of the fault‐free part of n‐node networks where nodes fail in a random dependent way. To capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, causing faults in the given node and its neighbors; faults at distance at most 2 become dependent...
Maňuch and Stacho (Theoret Inform Appl 37 (2003), 255–270) introduced the problem of designing f‐tolerant routings in optical networks, i.e. routings which still satisfy the given requests even if f failures occur in the network. In this article, we provide f‐tolerant routings in complete and complete balanced bipartite optical networks, optimal according to two parameters: the arc‐forwarding index...
The distance DG(v) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G. The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G. It is proved that for arbitrary graphs G and J and a positive integer r > 2, there exists a connected graph H, such that G is the antimedian and J the median subgraphs of...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.